package com.leaves.leetcode.array.t643_FindMaxAverage;


/**
 * 核心要点：
 * 固定长度滑动窗口
**/
 class Solution {
    /**
     * 固定长度滑动窗口
     * 1、这里其实用int就行，因为int最大为 2147483647 ~~ 2*10^9 满足要求
     * 2、转Double的方式不一定要用 Double.valueOf(x) 可以用1.0*x替代，在做除法时可以避免向下取证
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * @param nums
     * @param k
     * @return
     */
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        long subSum = 0;

        for (int i = 0; i < k; i++) subSum += nums[i];
        long maxSum = subSum;

        for (int i = k; i < n; i++) {
            subSum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, subSum);
        }
//        return Double.valueOf(maxSum)/k;
        return 1.0 * maxSum / n; // 这样也可以避免向下取整
    }
 }